{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #模糊搜索验证"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: articleMatch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #模糊搜索验证"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>请设计一个程序来支持用户在文本编辑器中的模糊搜索功能。用户输入内容中可能使用到如下两种通配符：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>'.'</code> 匹配任意单个字符。</li>\n",
    "\t<li><code>'*'</code> 匹配零个或多个前面的那一个元素。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>请返回用户输入内容 <code>input</code> 所有字符是否可以匹配原文字符串 <code>article</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>article = \"aa\", input = \"a\"\n",
    "<strong>输出:</strong> false\n",
    "<strong>解释:</strong> \"a\" 无法匹配 \"aa\" 整个字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>article = \"aa\", input = \"a*\"\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong>&nbsp;因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 \"aa\" 可被视为 'a' 重复了一次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>article = \"ab\", input = \".*\"\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong>&nbsp;\".*\" 表示可匹配零个或多个（'*'）任意字符（'.'）。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= article.length &lt;= 20</code></li>\n",
    "\t<li><code>1 &lt;= input.length &lt;= 20</code></li>\n",
    "\t<li><code>article</code> 只包含从 <code>a-z</code> 的小写字母。</li>\n",
    "\t<li><code>input</code> 只包含从 <code>a-z</code> 的小写字母，以及字符 <code>.</code> 和 <code>*</code> 。</li>\n",
    "\t<li>保证每次出现字符 <code>*</code> 时，前面都匹配到有效的字符</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 10&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/regular-expression-matching/\">https://leetcode-cn.com/problems/regular-expression-matching/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zheng-ze-biao-da-shi-pi-pei-lcof](https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zheng-ze-biao-da-shi-pi-pei-lcof](https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        if not p and not s:\n",
    "            return True\n",
    "        elif not p and s:\n",
    "            return False\n",
    "        fistmatch = False\n",
    "        if s and (p[0] == s[0] or p[0] == '.'):\n",
    "            fistmatch = True\n",
    "        if len(p) >= 2 and p[1] == '*':\n",
    "            if fistmatch:\n",
    "                return self.articleMatch(s[1:], p) or self.articleMatch(s, p[2:])\n",
    "            return self.articleMatch(s, p[2:])\n",
    "        return fistmatch and self.articleMatch(s[1:], p[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        if s=='' and p=='':\n",
    "            return True\n",
    "        elif s=='' and p!='':\n",
    "            if p.count('*')==len(p.replace('*','')):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif s!='' and p=='':\n",
    "            return False\n",
    "        else:\n",
    "            if p[-1]=='.':\n",
    "                return self.articleMatch(s[:-1],p[:-1])\n",
    "            elif p[-1]=='*':\n",
    "                if s[-1]==p[-2]:\n",
    "                    return self.articleMatch(s[:-1],p) or self.articleMatch(s[:-1],p[:-2]) or self.articleMatch(s,p[:-2])\n",
    "                elif p[-2]=='.':\n",
    "                    for i in range(len(s)+1):\n",
    "                        if self.articleMatch(s[:i],p[:-2]):\n",
    "                            return True\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return self.articleMatch(s,p[:-2])\n",
    "            else:\n",
    "                if s[-1]==p[-1]:\n",
    "                    return self.articleMatch(s[:-1],p[:-1])\n",
    "                else:\n",
    "                    return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        # dp[i][j] 代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配\n",
    "\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        # 初始化首行\n",
    "        '''\n",
    "        首行 s 为空字符串，因此当 p 的偶数位为 * 时才能够匹配（即让 p 的奇数位出现 0 次，保持 p 是空字符串）。\n",
    "        因此，循环遍历字符串 p ，步长为 2（即只看偶数位）\n",
    "        '''\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j-2] and p[j-1] == '*'\n",
    "\n",
    "        # 状态转移\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if p[j-1] == '*':\n",
    "                    if dp[i][j-2] or (dp[i-1][j] and s[i-1] == p[j-2]) or (dp[i-1][j] and p[j-2]=='.'):\n",
    "                        dp[i][j] = True # * 表示j-2出现一次\n",
    "                else:\n",
    "                    '''\n",
    "                    字符串 s 的前 i-1 个字符和 p 的前 j -1个字符匹配, 且s的第i个字符等于p的第j个字符;\n",
    "                    字符串 s 的前 i-1 个字符和 p 的前 j -1个字符匹配, 且p的第j个字符为'.';\n",
    "                    '''\n",
    "                    if (dp[i-1][j-1] and s[i-1] == p[j-1]) or (dp[i-1][j-1] and p[j-1] == '.'):\n",
    "                        dp[i][j] = True\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        if s=='' and p=='':\n",
    "            return True\n",
    "        elif s=='' and p!='':\n",
    "            if p.count('*')==len(p.replace('*','')):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif s!='' and p=='':\n",
    "            return False\n",
    "        else:\n",
    "            if p[-1]=='.':\n",
    "                return self.articleMatch(s[:-1],p[:-1])\n",
    "            elif p[-1]=='*':\n",
    "                if s[-1]==p[-2]:\n",
    "                    return self.articleMatch(s[:-1],p) or self.articleMatch(s[:-1],p[:-2]) or self.articleMatch(s,p[:-2])\n",
    "                elif p[-2]=='.':\n",
    "                    for i in range(len(s)+1):\n",
    "                        if self.articleMatch(s[:i],p[:-2]):\n",
    "                            return True\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return self.articleMatch(s,p[:-2])\n",
    "            else:\n",
    "                if s[-1]==p[-1]:\n",
    "                    return self.articleMatch(s[:-1],p[:-1])\n",
    "                else:\n",
    "                    return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        res = re.match(p, s)\n",
    "        return res is not None and res.end() == len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if p[j - 1] == '*':\n",
    "                    if dp[i][j - 2] == True:\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i - 1][j] and s[i - 1] == p[j - 2]:\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i - 1][j] and p[j - 2] == '.':\n",
    "                        dp[i][j] = True\n",
    "                else:\n",
    "                    if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]:\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i - 1][j - 1] and p[j - 1] == '.':\n",
    "                        dp[i][j] = True\n",
    "        \n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m = len(s) + 1\n",
    "        n = len(p) + 1\n",
    "        dp = [[False for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j-2] and p[j-1] == '*'\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if p[j-1] != '*':\n",
    "                    dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')\n",
    "                else:\n",
    "                    if dp[i][j-2]:\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'):\n",
    "                        dp[i][j] = True\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m = len(s)\n",
    "        n = len(p)\n",
    "        dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n + 1):\n",
    "            if dp[0][j-2] and p[j-1] == '*':\n",
    "                dp[0][j] = True\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if p[j-1] != \"*\":\n",
    "                    if dp[i-1][j-1] and (p[j-1] ==s[i-1] or p[j-1] =='.'):\n",
    "                        dp[i][j] =True\n",
    "                elif dp[i][j-2] or (dp[i-1][j] and s[i-1] == p[j-2]) or (dp[i-1][j] and p[j-2] =='.'):\n",
    "                    dp[i][j]=True\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        lens = len(s)\n",
    "        lenp = len(p)\n",
    "        dp = [[False for _ in range(lenp+1)] for _ in range(lens+1)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(lenp):\n",
    "            if p[j] == '*':\n",
    "                dp[0][j+1] |= dp[0][j-1]\n",
    "        for i in range(lens):\n",
    "            for j in range(lenp):\n",
    "                if s[i] == p[j] or p[j] == '.':\n",
    "                    dp[i+1][j+1] |= dp[i][j]\n",
    "                elif p[j] == '*':\n",
    "                    dp[i+1][j+1] |= dp[i+1][j-1]\n",
    "                    if s[i] == p[j-1] or p[j-1] == '.':\n",
    "                        dp[i+1][j+1] |= dp[i][j+1]\n",
    "        return dp[lens][lenp]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        if s=='' and p=='':\n",
    "            return True\n",
    "        elif s=='' and p!='':\n",
    "            if p.count('*')==len(p.replace('*','')):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif s!='' and p=='':\n",
    "            return False\n",
    "        else:\n",
    "            if p[-1]=='.':\n",
    "                return self.articleMatch(s[:-1],p[:-1])\n",
    "            elif p[-1]=='*':\n",
    "                if s[-1]==p[-2]:\n",
    "                    return self.articleMatch(s[:-1],p) or self.articleMatch(s[:-1],p[:-2]) or self.articleMatch(s,p[:-2])\n",
    "                elif p[-2]=='.':\n",
    "                    for i in range(len(s)+1):\n",
    "                        if self.articleMatch(s[:i],p[:-2]):\n",
    "                            return True\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return self.articleMatch(s,p[:-2])\n",
    "            else:\n",
    "                if s[-1]==p[-1]:\n",
    "                    return self.articleMatch(s[:-1],p[:-1])\n",
    "                else:\n",
    "                    return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m = len(p) + 1\n",
    "        n = len(s) + 1\n",
    "        dp = [[False] * m for _ in range(n)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, m, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                if p[j - 1] == '*': \n",
    "                    dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.')\n",
    "                else: \n",
    "                    dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m = len(s)\n",
    "        n = len(p)\n",
    "        dp = [[False]*(n+1) for _ in range(m+1)]\n",
    "        #初始化\n",
    "        dp[0][0] = True\n",
    "        for i in range(1,n+1):\n",
    "            if p[i-1] == '*':\n",
    "                dp[0][i] = dp[0][i-2]\n",
    "        \n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if s[i-1] == p[j-1] or p[j-1] == '.':\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                elif p[j-1] == '*':\n",
    "                    if s[i-1] == p[j-2] or p[j-2] == '.':\n",
    "                        dp[i][j] = dp[i-1][j] | dp[i][j-2]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j-2]\n",
    "        return dp[m][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m = len(s)\n",
    "        n = len(p)\n",
    "        dp = [[False]*(n+1) for i in range(m+1)]\n",
    "        dp[0][0] = True\n",
    "        def match(i, j):\n",
    "            if i == 0: return False\n",
    "            elif p[j-1] == '.': return True\n",
    "            else: return s[i-1] == p[j-1]\n",
    "        \n",
    "        for i in range(m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if match(i,j):\n",
    "                    dp[i][j] |= dp[i-1][j-1]\n",
    "                elif p[j-1] == '*':\n",
    "                    dp[i][j] |= dp[i][j-2]\n",
    "                    if match(i, j-1):\n",
    "                        dp[i][j] |= dp[i-1][j]\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        n,m=len(s)+1,len(p)+1\n",
    "        dp=[[False]*m for _ in range(n)]\n",
    "        dp[0][0]=True\n",
    "        for i in range(2,m,2):\n",
    "            dp[0][i]=dp[0][i-2] and p[i-1]=='*'\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,m):\n",
    "                if p[j-1]!='*':\n",
    "                    if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]: dp[i][j] = True # 5.\n",
    "                    elif dp[i - 1][j - 1] and p[j - 1] == '.': dp[i][j] = True    # 6.\n",
    "                else:\n",
    "                \t#1,2\n",
    "                    if dp[i][j-2] or dp[i][j-1]: dp[i][j]= True\n",
    "                     #3\n",
    "                    if dp[i-1][j] and s[i-1]==p[j-2]: dp[i][j]=True\n",
    "                     #4\n",
    "                    if dp[i-2][j] and p[j-2]=='.': dp[i][j]=True\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        return (re.fullmatch(p,s)) != None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        if s=='' and p=='':\n",
    "            return True\n",
    "        elif s=='' and p!='':\n",
    "            if p.count('*')==len(p.replace('*','')):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif s!='' and p=='':\n",
    "            return False\n",
    "        else:\n",
    "            if p[-1]=='.':\n",
    "                return self.articleMatch(s[:-1],p[:-1])\n",
    "            elif p[-1]=='*':\n",
    "                if s[-1]==p[-2]:\n",
    "                    return self.articleMatch(s[:-1],p) or self.articleMatch(s[:-1],p[:-2]) or self.articleMatch(s,p[:-2])\n",
    "                elif p[-2]=='.':\n",
    "                    for i in range(len(s)+1):\n",
    "                        if self.articleMatch(s[:i],p[:-2]):\n",
    "                            return True\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return self.articleMatch(s,p[:-2])\n",
    "            else:\n",
    "                if s[-1]==p[-1]:\n",
    "                    return self.articleMatch(s[:-1],p[:-1])\n",
    "                else:\n",
    "                    return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.') \\\n",
    "                           if p[j - 1] == '*' else \\\n",
    "                           dp[i - 1][j - 1] and (p[j - 1] == '.' or s[i - 1] == p[j - 1])\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m,n = len(s)+1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j-2] and p[j-1] == '*'\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if p[j-1] == '*':\n",
    "                    if dp[i][j -2]:\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i-1][j] and s[i-1] == p[j-2]:\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i-1][j] and p[j-2] == '.':\n",
    "                        dp[i][j] = True\n",
    "                else:\n",
    "                    if dp[i-1][j-1] and s[i-1] == p[j-1]:\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i-1][j-1] and p[j-1] == '.':\n",
    "                        dp[i][j] = True\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        n, m = len(s), len(p)\n",
    "        dp = [[False] * (m+1) for _ in range(n+1)]\n",
    "        dp[0][0] = True  # empty string\n",
    "        for j in range(2, m+1, 2):\n",
    "                dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1): \n",
    "                if p[j - 1] == '*':\n",
    "                    if dp[i][j - 2]: dp[i][j] = True                              # 1.\n",
    "                    elif dp[i - 1][j] and s[i - 1] == p[j - 2]: dp[i][j] = True   # 2.\n",
    "                    elif dp[i - 1][j] and p[j - 2] == '.': dp[i][j] = True        # 3.\n",
    "                else:\n",
    "                    if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]: dp[i][j] = True # 1.\n",
    "                    elif dp[i - 1][j - 1] and p[j - 1] == '.': dp[i][j] = True    # 2.\n",
    "\n",
    "        return dp[n][m]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        s_len = len(s)\n",
    "        p_len = len(p)\n",
    "\n",
    "        dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        def match(i ,j):\n",
    "            if i == 0:\n",
    "                return False\n",
    "            if p[j - 1] == '.':\n",
    "                return True\n",
    "            return s[i - 1] == p[j - 1]\n",
    "\n",
    "        for i in range(s_len + 1):\n",
    "            for j in range(1, p_len + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    dp[i][j] = dp[i][j - 2]\n",
    "                    if match(i, j - 1):\n",
    "                        dp[i][j] = dp[i][j] or dp[i - 1][j]\n",
    "                else:\n",
    "                    if match(i, j):\n",
    "                        dp[i][j] = dp[i - 1][j - 1]\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        s_len = len(s)\n",
    "        p_len = len(p)\n",
    "\n",
    "        dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        def match(i, j):\n",
    "            if i == 0:\n",
    "                return False\n",
    "            if p[j - 1] == '.':\n",
    "                return True\n",
    "            return s[i - 1] == p[j - 1]\n",
    "\n",
    "        for i in range(s_len + 1):\n",
    "            for j in range(1, p_len + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    dp[i][j] = dp[i][j - 2]\n",
    "                    if match(i, j - 1):\n",
    "                        dp[i][j] = dp[i][j] or dp[i - 1][j]\n",
    "                else:\n",
    "                    if match(i, j):\n",
    "                        dp[i][j] = dp[i - 1][j - 1]\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s), len(p)\n",
    "\n",
    "        def matches(i: int, j: int) -> bool:\n",
    "            if i == 0:\n",
    "                return False\n",
    "            if p[j - 1] == '.':\n",
    "                return True\n",
    "            return s[i - 1] == p[j - 1]\n",
    "\n",
    "        f = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        f[0][0] = True\n",
    "        for i in range(m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    f[i][j] |= f[i][j - 2]\n",
    "                    if matches(i, j - 1):\n",
    "                        f[i][j] |= f[i - 1][j]\n",
    "                else:\n",
    "                    if matches(i, j):\n",
    "                        f[i][j] |= f[i - 1][j - 1]\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        # 初始化首行\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        # 状态转移\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if p[j - 1] == '*':\n",
    "                    if dp[i][j - 2]: dp[i][j] = True                              # 1.\n",
    "                    elif dp[i - 1][j] and s[i - 1] == p[j - 2]: dp[i][j] = True   # 2.\n",
    "                    elif dp[i - 1][j] and p[j - 2] == '.': dp[i][j] = True        # 3.\n",
    "                else:\n",
    "                    if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]: dp[i][j] = True # 1.\n",
    "                    elif dp[i - 1][j - 1] and p[j - 1] == '.': dp[i][j] = True    # 2.\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        # 初始化首行\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        # 状态转移\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if p[j - 1] == '*':\n",
    "                    if dp[i][j - 2]: dp[i][j] = True                              # 1.\n",
    "                    elif dp[i - 1][j] and s[i - 1] == p[j - 2]: dp[i][j] = True   # 2.\n",
    "                    elif dp[i - 1][j] and p[j - 2] == '.': dp[i][j] = True        # 3.\n",
    "                else:\n",
    "                    if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]: dp[i][j] = True # 1.\n",
    "                    elif dp[i - 1][j - 1] and p[j - 1] == '.': dp[i][j] = True    # 2.\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m = len(p) + 1\n",
    "        n = len(s) + 1\n",
    "        dp = [[False] * m for _ in range(n)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, m, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                if p[j - 1] == '*': \n",
    "                    dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.')\n",
    "                else: \n",
    "                    dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        if s=='' and p=='':\n",
    "            return True\n",
    "        elif s=='' and p!='':\n",
    "            if p.count('*')==len(p.replace('*','')):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif s!='' and p=='':\n",
    "            return False\n",
    "        else:\n",
    "            if p[-1]=='.':\n",
    "                return self.articleMatch(s[:-1],p[:-1])\n",
    "            elif p[-1]=='*':\n",
    "                if s[-1]==p[-2]:\n",
    "                    return self.articleMatch(s[:-1],p) or self.articleMatch(s[:-1],p[:-2]) or self.articleMatch(s,p[:-2])\n",
    "                elif p[-2]=='.':\n",
    "                    for i in range(len(s),-1,-1):\n",
    "                        if self.articleMatch(s[:i],p[:-2]):\n",
    "                            return True\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return self.articleMatch(s,p[:-2])\n",
    "            else:\n",
    "                if s[-1]==p[-1]:\n",
    "                    return self.articleMatch(s[:-1],p[:-1])\n",
    "                else:\n",
    "                    return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.') if p[j - 1] == '*' else dp[i - 1][j - 1] and (p[j - 1] == '.' or s[i - 1] == p[j - 1])\n",
    "        return dp[-1][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s), len(p)\n",
    "        dp = [[False for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, n+1):\n",
    "            if p[i-1] == '*': dp[0][i] = dp[0][i-2]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if p[j-1] == '.' or p[j-1] == s[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                elif p[j-1] == '*':\n",
    "                    if s[i-1] != p[j-2] and p[j-2] != '.':\n",
    "                        dp[i][j] = dp[i][j-2]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j-1] | dp[i-1][j] | dp[i][j-2]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.') \\\n",
    "                           if p[j - 1] == '*' else \\\n",
    "                           dp[i - 1][j - 1] and (p[j - 1] == '.' or s[i - 1] == p[j - 1])\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for j in range(2, len(p) + 1):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "\n",
    "        for i in range(1, len(s) + 1):\n",
    "            for j in range(1, len(p) + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.'))\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')\n",
    "\n",
    "        return dp[len(s)][len(p)]\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.') \\\n",
    "                           if p[j - 1] == '*' else \\\n",
    "                           dp[i - 1][j - 1] and (p[j - 1] == '.' or s[i - 1] == p[j - 1])\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s), len(p)\n",
    "\n",
    "        def matches(i: int, j: int) -> bool:\n",
    "            if i == 0:\n",
    "                # 代表s这边没有前置序列可与p匹配\n",
    "                return False\n",
    "            if p[j - 1] == '.':\n",
    "                return True\n",
    "            return s[i - 1] == p[j - 1]\n",
    "\n",
    "        f = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        f[0][0] = True\n",
    "        for i in range(m + 1):\n",
    "            # 因为*的存在直接跳过p的第1个\n",
    "            for j in range(1, n + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    # 确认跳过前一符号是否能匹配上\n",
    "                    f[i][j] |= f[i][j - 2]\n",
    "                    if matches(i, j - 1):\n",
    "                        f[i][j] |= f[i - 1][j]\n",
    "                else:\n",
    "                    if matches(i, j):\n",
    "                        f[i][j] |= f[i - 1][j - 1]\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        length1, length2 = len(s), len(p)\n",
    "        dp = [[False for _ in range(length2 + 1)] for _ in range(length1 + 1)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(1, length2 + 1):\n",
    "            if p[j - 1] == '*':\n",
    "                dp[0][j] = dp[0][j - 2]\n",
    "        for i in range(1, length1 + 1):\n",
    "            dp[i][0] = False\n",
    "        for j in range(1, length2 + 1):\n",
    "            for i in range(1, length1 + 1):\n",
    "                if p[j - 1] == '.' or s[i - 1] == p[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                elif p[j - 1] == '*':\n",
    "                    dp[i][j] = dp[i][j - 2]\n",
    "                    if p[j - 2] == '.' or p[j - 2] == s[i - 1]:\n",
    "                        dp[i][j] = dp[i][j] or dp[i - 1][j]\n",
    "        return(dp[length1][length2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m = len(s) + 1\n",
    "        n = len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2,n,2):\n",
    "            dp[0][j] = dp[0][j-2] and p[j-1] == '*'\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if p[j-1] == '*':\n",
    "                    if dp[i][j-2]:\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i-1][j] and s[i-1] == p[j-2]:\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i-1][j] and p[j-2] == '.':\n",
    "                        dp[i][j] = True\n",
    "                else:\n",
    "                    if dp[i-1][j-1] and ( s[i-1] == p[j-1] or p[j-1] == '.'):\n",
    "                        dp[i][j] = True\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://mp.weixin.qq.com/s/rnaFK05IcFWvNN1ppNf2ug\n",
    "# 当p[j + 1]为*通配符时，我们分情况讨论下：\n",
    "\n",
    "# 1、如果匹配，即s[i] == p[j]，那么有两种情况：\n",
    "\n",
    "# 1.1p[j]有可能会匹配多个字符，比如s = \"aaa\", p = \"a*\"，那么p[0]会通过*匹配 3 个字符\"a\"。\n",
    "\n",
    "# 1.2p[i]也有可能匹配 0 个字符，比如s = \"aa\", p = \"a*aa\"，由于后面的字符可以匹配s，所以p[0]只能匹配 0 次。\n",
    "\n",
    "# 2、如果不匹配，即s[i] != p[j]，只有一种情况：\n",
    "\n",
    "# p[j]只能匹配 0 次，然后看下一个字符是否能和s[i]匹配。比如说s = \"aa\", p = \"b*aa\"，此时p[0]只能匹配 0 次。\n",
    "\n",
    "# 综上，可以把之前的代码针对*通配符进行一下改造：\n",
    "\n",
    "# 动态规划算法的核心就是「状态」和「选择」，「状态」无非就是i和j两个指针的位置，「选择」就是p[j]选择匹配几个字符。\n",
    "\n",
    "# 我觉得这道题不掌握也行，考的概率也很小\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = []\n",
    "\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s), len(p)\n",
    "        # 备忘录\n",
    "        self.memo = [[-1] * n for _ in range(m)]\n",
    "\n",
    "        # 指针 i，j 从索引 0 开始移动\n",
    "        return self.dp(s, 0, p, 0)\n",
    "\n",
    "    # 计算 p[j..] 是否匹配 s[i..]。最终结果是要求p[0..]是否匹配s[0..]\n",
    "    def dp(self, s, i, p, j):\n",
    "        m, n = len(s), len(p)\n",
    "\n",
    "        # base case 1\n",
    "        if j == n:\n",
    "            return i == m\n",
    "        # base case 2\n",
    "        if i == m: # 意思就是循环到：把s都循环完了的，下一位空位。同理j，j也是循环到了匹配完所有s，的下一位（非空位）\n",
    "            if (n - j) % 2:\n",
    "                return False\n",
    "            for k in range(j, n, 2):\n",
    "                if p[k+1] != \"*\":\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # 消除重叠子问题\n",
    "        if self.memo[i][j] != -1:\n",
    "            return self.memo[i][j]\n",
    "\n",
    "        # 初始化res\n",
    "        res = False\n",
    "        if s[i] == p[j] or p[j] == \".\":\n",
    "            if j+1 < n and p[j+1] == \"*\":\n",
    "                # *会匹配0次或1次及以上，用or链接\n",
    "                # 这里是匹配0次的情况：p[i]也有可能匹配 0 个字符，比如s = \"aa\", p = \"a*aa\"，由于后面的字符可以匹配s，所以p[0]只能匹配 0 次\n",
    "                res = self.dp(s, i, p, j+2) or self.dp(s, i+1, p, j)\n",
    "\n",
    "            else:\n",
    "                res = self.dp(s, i+1, p, j+1)\n",
    "        else:\n",
    "            if j+1 < n and p[j+1] == \"*\":\n",
    "                res = self.dp(s, i, p, j+2)\n",
    "            else:\n",
    "                return False\n",
    "                \n",
    "        \n",
    "        # 将当前结果记入备忘录\n",
    "        self.memo[i][j] = res\n",
    "        return self.memo[i][j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.') \\\n",
    "                           if p[j - 1] == '*' else \\\n",
    "                           dp[i - 1][j - 1] and (p[j - 1] == '.' or s[i - 1] == p[j - 1])\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        n1, n2 = len(s), len(p)\n",
    "        # dp[i][j] means if s[:i] and p[:j] matches\n",
    "        dp = [[False] * (n2 + 1) for _ in range(n1 + 1)]\n",
    "        # corner cases: \n",
    "        # dp[0][j] = p[j-2] == '*'\n",
    "        # dp[i][0] = False\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n2 + 1):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        # Transition rule:\n",
    "        # s[i + 1] == p[j + 1] or '.' : dp[i][j] = dp[i - 1][j - 1]\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    dp[i][j] = dp[i][j - 1] or (j > 1 and dp[i][j - 2])\n",
    "                    if p[j - 2] in [s[i - 1], '.']:\n",
    "                        dp[i][j] |= dp[i - 1][j]\n",
    "                else:\n",
    "                    dp[i][j] = p[j - 1] in [s[i - 1], '.'] and dp[i - 1][j - 1]\n",
    "        return dp[n1][n2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s), len(p)\n",
    "        dp = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(1, n + 1):\n",
    "            if p[j - 1] == '*':\n",
    "                dp[0][j] = dp[0][j - 2]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if s[i - 1] == p[j - 1] or p[j - 1] == '.':\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                if p[j - 1] == '*':\n",
    "                    dp[i][j] = dp[i][j - 2]\n",
    "                    if s[i - 1] == p[j - 2] or p[j - 2] == '.':\n",
    "                        dp[i][j] |= dp[i - 1][j]\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.') \\\n",
    "                           if p[j - 1] == '*' else \\\n",
    "                           dp[i - 1][j - 1] and (p[j - 1] == '.' or s[i - 1] == p[j - 1])\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        # 初始化首行\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        # 状态转移\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if p[j - 1] == '*':\n",
    "                    if dp[i][j - 2]: dp[i][j] = True                              # 1.\n",
    "                    elif dp[i - 1][j] and s[i - 1] == p[j - 2]: dp[i][j] = True   # 2.\n",
    "                    elif dp[i - 1][j] and p[j - 2] == '.': dp[i][j] = True        # 3.\n",
    "                else:\n",
    "                    if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]: dp[i][j] = True # 1.\n",
    "                    elif dp[i - 1][j - 1] and p[j - 1] == '.': dp[i][j] = True    # 2.\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s), len(p)\n",
    "        f = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        f[0][0] = True\n",
    "        for j in range(1, n + 1):\n",
    "            if p[j - 1] == '*': f[0][j] = f[0][j - 2]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if p[j - 1] == '.' or s[i - 1] == p[j - 1]:\n",
    "                    f[i][j] = f[i - 1][j - 1]\n",
    "                elif p[j - 1] == '*':\n",
    "                    if s[i - 1] != p[j - 2] and p[j - 2] != '.':\n",
    "                        f[i][j] = f[i][j - 2]\n",
    "                    else:\n",
    "                        f[i][j] = f[i-1][j] | f[i][j-2]\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        len_s = len(s)\n",
    "        len_p = len(p)\n",
    "\n",
    "        dp = [[False] * (len_p + 1) for _ in range(len_s + 1)]\n",
    "        dp[0][0] = True\n",
    "        def match(i, j):\n",
    "            if i == 0:\n",
    "                return False\n",
    "            if p[j - 1] == '.':\n",
    "                return True\n",
    "            return s[i - 1] == p[j - 1]\n",
    "\n",
    "        for i in range(len_s + 1):\n",
    "            for j in range(1, len_p + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    dp[i][j] = dp[i][j - 2]\n",
    "                    if match(i, j - 1):\n",
    "                        dp[i][j] = dp[i][j] or dp[i - 1][j]\n",
    "                else:\n",
    "                    if match(i, j):\n",
    "                        dp[i][j] = dp[i - 1][j - 1]\n",
    "\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m = len(p) + 1\n",
    "        n = len(s) + 1\n",
    "        dp = [[False] * m for _ in range(n)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, m, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                if p[j - 1] == '*': \n",
    "                    dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.')\n",
    "                else: \n",
    "                    dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        n, m = len(s), len(p)\n",
    "        dp = [[False] * (m + 1) for _ in range(n + 1)]\n",
    "\n",
    "        dp[0][0] = True\n",
    "        for i in range(2, m + 1, 2):\n",
    "            dp[0][i] = dp[0][i - 2] and p[i - 1] == '*'\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.'))\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        # s:input, p:article\n",
    "         res = re.search(p,s)\n",
    "         return bool(res and res.group() == s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m, n = len(s) + 1, len(p) + 1\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        for j in range(2, n, 2):\n",
    "            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if p[j - 1] == '*':\n",
    "                    if dp[i][j - 2]: dp[i][j] = True\n",
    "                    elif dp[i - 1][j] and s[i - 1] == p[j - 2]: dp[i][j] = True\n",
    "                    elif dp[i - 1][j] and p[j - 2] == '.':dp[i][j] = True\n",
    "                else:\n",
    "                    if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]: dp[i][j] = True\n",
    "                    elif dp[i - 1][j - 1] and p[j - 1] == '.': dp[i][j] = True\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        p_seg = []\n",
    "        i = 0\n",
    "        while i < len(p):\n",
    "            if i + 1 < len(p) and p[i + 1] == \"*\":\n",
    "                p_seg.append(p[i:i + 2])\n",
    "                i += 2\n",
    "            else:\n",
    "                p_seg.append(p[i])\n",
    "                i += 1\n",
    "        ls, lp = len(s), len(p_seg)\n",
    "        f = [[False] * (ls + 1) for _ in range(lp + 1)]\n",
    "        f[0][0] = True\n",
    "        for i in range(lp):\n",
    "            f[i + 1][0] = (f[i][0] and len(p_seg[i]) == 2)\n",
    "            for j in range(ls):\n",
    "                if p_seg[i][0] == \".\" or p_seg[i][0] == s[j]:\n",
    "                    if len(p_seg[i]) == 2 and f[i + 1][j]:\n",
    "                        f[i + 1][j + 1] = True\n",
    "                        continue\n",
    "                    k = i - 1\n",
    "                    while k >= 0 and len(p_seg[k]) == 2:\n",
    "                        if f[k + 1][j]:\n",
    "                            f[i + 1][j + 1] = True\n",
    "                            break\n",
    "                        k -= 1\n",
    "                    if k >= -1 and f[k + 1][j]:\n",
    "                        f[i + 1][j + 1] = True\n",
    "        i = lp - 1\n",
    "        while i >= 0 and len(p_seg[i]) == 2:\n",
    "            if f[i + 1][ls]:\n",
    "                return True\n",
    "            i -= 1\n",
    "        return f[i + 1][ls]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        pattern=re.compile(p)\n",
    "        result=pattern.match(s)\n",
    "        return result.group()==s if result else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        s_len = len(s)\n",
    "        p_len = len(p)\n",
    "\n",
    "        dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        def match(i, j):\n",
    "            if i == 0:\n",
    "                return False\n",
    "            if p[j - 1] == '.':\n",
    "                return True\n",
    "            return s[i - 1] == p[j - 1]\n",
    "\n",
    "        for i in range(s_len + 1):\n",
    "            for j in range(1, p_len + 1):\n",
    "                if p[j - 1] == '*':\n",
    "                    dp[i][j] = dp[i][j - 2]\n",
    "                    if match(i, j - 1):\n",
    "                        dp[i][j] = dp[i][j] or dp[i - 1][j]\n",
    "                else:\n",
    "                    if match(i, j):\n",
    "                        dp[i][j] = dp[i - 1][j - 1]\n",
    "        print(dp)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        m,n=len(s)+1,len(p)+1\n",
    "        dp=[[False]*n for _ in range(m)]\n",
    "        dp[0][0]=True\n",
    "        for j in range(2,n,2):\n",
    "            dp[0][j]=dp[0][j-2] and p[j-1]=='*'\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if p[j-1]=='*':\n",
    "                    if dp[i][j-2]:dp[i][j]=True\n",
    "                    elif dp[i-1][j] and s[i-1]==p[j-2]:dp[i][j]=True\n",
    "                    elif dp[i-1][j] and p[j-2]=='.':dp[i][j]=True\n",
    "                else:\n",
    "                    if dp[i-1][j-1] and s[i-1]==p[j-1]:dp[i][j]=True\n",
    "                    elif dp[i-1][j-1] and p[j-1]=='.':dp[i][j]=True\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j == n:\n",
    "                return i == m\n",
    "            if j + 1 < n and p[j+1] == '*':\n",
    "                return dfs(i, j + 2) or (i < m and \\\n",
    "                       (s[i] == p[j] or p[j] == '.') and dfs(i + 1, j))\n",
    "            return i < m and (s[i] == p[j] or p[j] == '.') \\\n",
    "                   and dfs(i + 1, j + 1)\n",
    "        m, n = len(s), len(p)\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def articleMatch(self, s: str, p: str, cache=None) -> bool:\n",
    "\n",
    "        def trim(pattern: str) -> str:\n",
    "            if len(pattern) >= 4 and pattern[1] == \"*\" and pattern[0:2]*2 == pattern[0:4]:\n",
    "                return trim(pattern[2:])\n",
    "            return pattern\n",
    "\n",
    "        p = trim(p)\n",
    "\n",
    "        # cache = cache or dict()\n",
    "        # cache_key = f\"{s}@@{p}\"\n",
    "        # if cache_key in cache:\n",
    "        #     return cache[cache_key]\n",
    "\n",
    "        if s and not p:\n",
    "            return False\n",
    "        \n",
    "        if p in (s, s+\"*\", \".*\"):\n",
    "            return True\n",
    "        \n",
    "        result = None\n",
    "        if len(p) > 1 and p[1] == \"*\":\n",
    "            if s and p[0:2] in (\".*\", s[0]+\"*\"):\n",
    "                result = any(\n",
    "                    [\n",
    "                        self.articleMatch(s[1:], p[2:], cache=cache), \n",
    "                        self.articleMatch(s[1:], p, cache=cache),\n",
    "                        self.articleMatch(s, p[2:], cache=cache), \n",
    "                    ]\n",
    "                )  \n",
    "            else:\n",
    "                result = self.articleMatch(s, p[2:], cache=cache)\n",
    "        else:\n",
    "            result = s and p[0] in (\".\", s[0]) and self.articleMatch(s[1:], p[1:], cache=cache)\n",
    "        \n",
    "        # cache[cache_key] = result\n",
    "        return bool(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def articleMatch(self, s: str, p: str) -> bool:\n",
    "        def match(i, j):\n",
    "            nonlocal s, p\n",
    "            if j == -1:\n",
    "                return False\n",
    "            if i == -1:\n",
    "                if j == 1 and p[j] == \"*\":\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if s[i] == p[j] or p[j] == \".\":\n",
    "                return True\n",
    "            return False\n",
    "        m, n = len(s), len(p)\n",
    "        dp = [[False for i in range(n + 1)] for j in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        if len(p) >= 2 and match(-1, 1):\n",
    "            dp[0][2] = True\n",
    "        for i in range(m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if p[j - 1] == \"*\":\n",
    "                    if match(i - 1, j - 2):\n",
    "                        dp[i][j] = dp[i][j - 2] | dp[i - 1][j]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j - 2]\n",
    "                else:\n",
    "                    if match(i - 1, j - 1):\n",
    "                        dp[i][j] = dp[i - 1][j - 1]\n",
    "        print(dp)\n",
    "        return dp[m][n]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
